As used herein, “memory” in a digital computer refers to a physical device that can store data in it and from which the data can be retrieved. Thus, the term “memory” as used herein encompasses random access main memory, such as static or dynamic random access memory integrated circuit chips, as well as direct access data storage, such as disk drives.
As used herein, “dynamic allocation of memory” is the allocation of data storage locations in memory as the data storage locations are needed during execution of a program, so that a set of allocated data storage locations is assigned to a program task. For example, an array is a set of contiguous data storage locations named in a computer program.
A digital computer typically includes memory and an operating system program that permits the memory to be dynamically allocated and freed during execution of an application program. The process of dynamically allocating and freeing the memory typically results in the data in the memory becoming sparsely accessed. To deal with this problem, a dynamic data structure is often used for managing access to the sparsely-accessed data. The dynamic data structure itself grows and shrinks dynamically as the memory is allocated and freed. However, the natural tendency is for the dynamic data structure to grow until reaching a limit set in the operating system program. In addition, this growth of the dynamic data structure typically does not reduce the processing time for managing access to the sparsely-accessed data. Instead, the performance may degrade as the dynamic data structure grows and reaches the limit set in the operating system program.
For example, the operating system of a digital computer typically permits an application process to sparsely access data in a virtual address space. The operating system typically maintains a dynamic data structure in the form of a multilevel table for translating the virtual addresses to physical memory addresses. Such multilevel tables are used in the Intel Corporation x86, Sun Corporation SPARC, and other central processing unit (CPU) architectures. During use, the memory that is dynamically allocated to the application programs tends to become distributed over the virtual address space. Consequently, the multilevel table tends to grow in size until reaching a limit set in the operating system program.